
<!-- saved from url=(0050)http://www.courses.ncsu.edu/csc501/lec/001/hw/hw4/ -->
<HTML><HEAD><META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<TITLE>Homework 4</TITLE>
<STYLE>
<!--
	body{
		padding: 10px;
	}

	td{
		background: #fff;
	}

	.header{
		 background: #eee;
		 font-weight: bold;
	}

	.problem{
		margin-top: 50px;
	}
-->
</STYLE>
</HEAD><BODY>
<H3>Homework 4</H3>
<P>
Deadline: see web page Assignments: Please use the machine osXX.csc.ncsu.edu (Linux) XX=40-55. All programs have to be written in C, translated with gcc and turned in with a corresponding Makefile. Problems 3 is to be solved in the groups of 3 students, problems 1 and 2 are to be solved individually.
</P>
<P>
You may find code on the web that solves parts of these exercises. Feel free to browse this code, read it, learn from it. However, do not copy any code to solve this assignment.
</P>

<OL>
<!--p1 start-->
<LI>
<P>Turn in file problem1.txt</P>
<OL type="a">
<LI>In free disk space management, what is the tradeoff between threading and copying? How does the Log-structured File System (LFS) manage free disk space. </LI>
<LI>What is <EM>write cost</EM>? For 5 segments with utilization 0.8, 0.7, 0.2, 0.3, and 0.6 respectively, what is the write cost (assuming seeks and rotational latency are negligible)?</LI>
<LI>Briefly describe why the greedy segment cleaning policy cannot create a bimodal segment distribution when the access pattern shows locality. How this problem is solved in LFS? </LI>
</OL>
</LI>
<!--p1 end-->

<!--p2 start-->
<LI>
<P>Suppose that a disk drive has 4,000 cylinders numbered 0 to 3,999. The drive is currently serving a request at cylinder 255, and the previous request was at cylinder 250. The queue of pending requests, in FIFO order, is </P>
<PRE>442,  30,  3389,  10,  2053,  110,  929,  2291,  1186,  581</PRE>
<P>Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all pending requests for each of the following disk-scheduling algorithms?
</P><UL>
<LI>SSTF</LI>
<LI>LOOK</LI>
<LI>C-LOOK (assuming fast-return from highest to lowest cylinder)</LI>
<LI>5-step LOOK</LI>
<LI>F-LOOK (requests are served at the rate such that 4, 3, 5 [or whatever remains] requests make it into a queue, respectively, before being served)</LI>
</UL>
<P></P>
<P>
Turn in file problem2.txt
</P>
</LI>
<!--p2 end-->

<P>
     </P><LI>(80 points) The purpose of this assignment is to understand
       how buffer overflows work and how to exploit memory protection
       to prevent them. This may not be the most efficient way to
       address buffer overflows, yet it exposes you to memory
       protection from an interesting point of few. Caution: Some
       assembly required, but not much, and we'll learn all of this. We
       will approach the problem in several steps. (The original
       problem is due to Andrew Appel. We have enhanced it with the
       sandbox protection problem.)

       <P>
       <B>Background:</B> We will provide you a program, both source
       code (hello.c) and executable binary code (hello). The file
       hello was produced from hello.c using the gcc command with the
       -O1 option.  The program asks you your name, and prints out
       something like this (this is how Princeton determines grades ---
       just kidding):

       </P><PRE>       % hello
       What is your name?
       Frank
       Thank you, Frank.
       I recommend that you get a grade of F on this assignment.
       </PRE>

       Your job is to provide input "data" to this program so that it
       prints something more like this:

       <PRE>       % trigger a |hello
       What is your name?
       Thank you, Frank.
       I recommend that you get a grade of A on this assignment.
       </PRE>

       You are to design a program <B>trigger</B> that takes as a
       parameter the letter grade (a/b/c/d/s) that it should print
       out using variants of buffer overflow attacks. (We'll get to
       parameter 's' later.)
       <P>
       As you can see from reading the program hello (provided below),
       it is not designed to give anyone an A under any
       circumstances. However, it is programmed sloppily: it reads the
       input into a buffer, but forgets to check whether the input
       fits. This means that a too-long input can overwrite other
       important memory, and you can trick the program into giving you
       an A.

       </P><UL>

       <LI> (10 points) Analyze the program.  Take the hello executable
       binary file that we have provided you, and use gdb to analyze
       its sections:

	 <UL>
	 <LI> Analyze the text section by issuing this command:

	 <PRE>	 % gdb hello
	 (gdb) disassem readString
	 </PRE>

	 Copy the resulting lines of text into a text file named
	 hello.dis, and then annotate the code to explain what's going
	 on. You should use the source code in hello.c as a reference,
	 and indeed your annotation should just consist of showing how
	 the machine code corresponds to the C code. You don't need an
	 annotation for every line of machine code.

	 </LI><LI> Analyze the data section by issuing these "print" commands:

	 <PRE>
	 % gdb hello
	 (gdb) print &amp;grade
	 (gdb) print grade
	 </PRE>

	 Place a diagram in your hello.dis file showing the layout of the
	 data section.

	 </LI><LI> Analyze the bss section by issuing this "print" command:

	 <PRE>	 % gdb hello
	 (gdb) print &amp;Name
	 </PRE>

	 Place a diagram in your hello.dis file showing the layout of the
	 bss section.

	 </LI><LI> Analyze the readString function's stack-frame. It will be
	 most informative to analyze the stack-frame after the function
	 has read a name into buf. Issue these commands to do that:

	 <PRE>	 % gdb hello
	 What is your name?
	 (gdb) break readString
	 (gdb) run
	 (gdb) print $r1
	 (gdb) continue
	 Frank
	 (gdb) break *readString+92
	 (gdb) print buf
	 (gdb) print &amp;buf
	 (gdb) x/??b $rsp+??  (where ?? is the appropriate number of bytes)
	 </PRE>

	 Place a diagram of the stack frame layout, indicating
	 addresses relative to the stack pointer in your hello.dis file.

	 </LI></UL>

      </LI><LI> (5 points) Get the program to crash.  Write a D program
      named trigger.c that upon input parameter 'd' produces some
      output. Upon using this output as an input for hello (e.g. using
      an intermediate file or a pipe), hello will generate a
      segmentation fault. 
      <PRE>       % trigger d |hello
       What is your name?
       Segmentation fault
      </PRE>
      Explain its principles of operation in one sentence as a comment
      within your trigger.c program.

      </LI><LI> (10 points) Get hello to print
      "C".  Extend trigger.c with parameter 'c' such that its output
      used as input to hello causes the hello program
      to print your name and recommend a grade of "C". You can see by
      reading the program that, if your name is Andrew Appel, this is
      very easy to do. But probably your name isn't Andrew Appel.
      <PRE>       % trigger c |hello
       What is your name?
       Thank you, Frank                               .
       I recommend that you get a grade of C on this assignment.
      </PRE>
      Recommended method: Overrun the buffer with a return address that
      jumps to a place inside of the main function.

      </LI><LI> (20 points) Get the hello program to print "B".  Extend
      trigger.c with parameter 'b' such that its output used as input
      to hello causes the hello program to print your name and
      recommend a grade of "B".
      <PRE>
       % trigger b |hello
       What is your name?
       Thank you, Frank.
       I recommend that you get a grade of B on this assignment.
      </PRE>
      Recommended method: Overrun the buffer with a three-part
      byte-sequence: (1) your name, (2) a return address that points
      into same string with a known, fixed address, and
      (3) a short machine-language program that
      stores a 'B' into the right place and then jumps somewhere
      useful. This program should just have a few instructions that
      operate on an available register and use op codes similar to the
      ones you already encounter in the program (but maybe on different
      registers). Hence, you may want to read up on x86-64 instruction
      encodings (see link below) and verify your code (using the
      disassem commend in gdb on your string address) before actually
      executing the code.
      <P>
      If your name is very longer than 6
      characters, you may use a nickname of up to 6 characters.

      </P></LI><LI> (10 points) You can make buffer overflow attacks more
      difficult by using randomization (but you cannot prevent them) by stack
      randomization. This is simulated by calling "hello r" as an extra e bytes
     are allocated the stack, where e is is a
     random integer between 0 and 31. by Get the hello program with
     parameter r to <B>always</B>
     print "A".  Extend
     trigger.c with parameter 'a' such that its output used as input
     to "hello r" causes the hello program to print your name and
     recommend a grade of "A" <B>on each invocation</B>, 
     regardless of randomozation.
     <PRE>
      % trigger a |hello r
      What is your name?
      Thank you, Frank.
      I recommend that you get a grade of A on this assignment.
     </PRE>
     Recommended method: Same as for B except that you need to put
     return addresses / fixed addresses in multiple locations.
     <P>
     If your name is very longer than 6
     characters, you may use a nickname of up to 6 characters.

     </P></LI><LI> (25 points) Actually, style 'a' and 'b' overflows cannot happen in
     our system due to execution restrictions on global data (see
     notes below), but style 'c' overflows can occur. Design a sandbox
     approach using memory protection to detect buffer overflow
     attacks (actually just those that divert control upon return from
     a function). Extend trigger.c with parameter 's' such that its
     output causes a buffer overflow (style 'c') but for binary hello3
     (which has different offsets than hello). Initially, it should still print
     "C" for trigger with parameter 's' as input to
     hello3 (the new version of hello). 
     <PRE>      % trigger s |hello3
      What is your name?
      Thank you, Frank                               .
      I recommend that you get a grade of C on this assignment.
     </PRE>
     Once you have finished this
     part of the assignment, it should cause hello3 program to
     detect your violation attempt as follows: 
     <PRE>
     % trigger s |hello3 s 
     What is your name?
     malicious buffer overflow detected, will exit!
     </PRE>
     Notice that hello3 is called with parameter 's' in this case,
     i.e., the sandbox option is only acticated with this parameter to
     hello3. Without it, the "C" overflow still works. This allows you
     to test both versions on the same executables.
     Recommended method: Use the files hello3.c and readString.c to
     separate each function of the program into its own module (object
     file). Notice that hello3 does not provide execute rights for the
     page that Name resides on. It also initializes a new module,
     sandbox.c, which you have to write. Each module should be
     separated by a long enough sequence of "nop" instruction
     (automatically generated by genpage within the Makefile) so that,
     once linked, each function resides within a different 4k memory
     page. You should now manipulate the memory protection using the
     mprotect() system call (see man page). 
     <P>
     Initially, all code pages
     have read and execute permission except for the readString page
     that lacks execute permission. Now, establish a signal handler
     using sigaction() with SA_RESTART and SA_SIGINFO flags for signal
     SIGSEGV and unblock the signal.
     </P><P>
     Inside the signal handler, you can establish the address where
     the SEGV occurred using the 2nd parameter (siginfo_t *) of the
     handler, specifically through the si_addr structure element, and
     the stack pointer using the 3rd parameter (ucontext_t *).
     </P><P>
     If you SEGV on entering a new function, record return address, unprotect the
     page (read permission) corresponding to the SEGV addr and protect
     the page that your call originated from. Conversely, upon a SEGV
     at the return from a function, unprotect the target page of the
     return and protect the page of the function you are returning
     from.
     </P><P>
     Now, add a check on the return from a function to ensure that the
     target address of the return matches the return address that your stored at an
     earlier entry point to the function. In effect, you have
     implemented a software scheme equivalent to the hardware
     mechanism of SmashGuard. Notice: Your sandbox code only has
     to work for the hello3/readString sample code.

     </P></LI></UL>

     Helpful links:

     <UL>

     <LI><A href="http://www.cs.cmu.edu/~fp/courses/15213-s06/misc/asm64-handout.pdf">x86-64 Machine-Level Programming</A>
     </LI><LI><A href="http://www.classes.cs.uchicago.edu/archive/2009/spring/22620-1/docs/handout-03.pdf">x86-64 Instructions and ABI</A>
     </LI></UL>

    
     Implementation Notes:

     <UL>

     <LI>On some versions of Linux, every time the program is executed
     the initial stack pointer is in a different place. This makes it
     difficult to make an attack in which the return address points
     into the same data that was just read into the buffer on the
     stack. (Indeed, that is the purpose of varying the initial stack
     pointer!) However, you'll note that the data is copied from "buf"
     into "Name". You'll find that "Name" is reliably in the same
     place every time you (or we) run the program.

     </LI><LI> On some versions of Linux, executing instructions from the
     data section causes a segmentation violation. The purpose of this
     is to defend against buffer overrun attacks! The "mprotect" call
     in our sample program is to disable this protection. You're not
     required to understand or explain how this line works. Note,
     however, that this mechanism (even if we didn't disable it) would
     not defend against the "B" attack.

     </LI><LI> If you work hard, you could create a data input that will
     exploit the buffer overrun to take over the grader's Linux
     process and do all sorts of damage. DO NOT DO THIS! Any
     deliberate attempt of this sort is a violation of the
     University's disciplinary code, and is also a violation of the
     Computer Fraud and Abuse Act: 
     <P>
     "If you were to use a buffer overrun attack to knowingly gain
     unauthorized access or to cause damage to other people's
     computers, the Computer Fraud and Abuse Act provides a maximum
     penalty of _______ years in prison for a first offense. However,
     the creator of the Melissa virus plea-bargained down to ______
     months in prison."

     </P></LI></UL>

      <P class="dataFollows">The following files are provided to solve this
        exercise:</P>

      <UL>
        <LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw4/q3/Makefile"><CODE>Makefile</CODE></A>
        </LI><LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw4/q3/genpage.c"><CODE>genpage.c</CODE></A>
        </LI><LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw4/q3/hello.c"><CODE>hello.c</CODE></A>
        </LI><LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw4/q3/hello"><CODE>hello</CODE></A>
        </LI><LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw4/q3/readString.c"><CODE>readString.c</CODE></A>

        </LI><LI><A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw4/q3/hello3.c"><CODE>hello3.c</CODE></A>
      </LI></UL>

      <P class="dataFollows">The following files have to be turned in for this
        exercise (without <STRONG>any</STRONG> activated debugging output):</P>
      <UL>

        <LI><CODE>hello.dis</CODE></LI>
        <LI><CODE>trigger.c</CODE></LI>
        <LI><CODE>sandbox.c</CODE></LI>
      </UL>

    </LI>


<P>

   </P><LI>Peer evaluation: Each group members has to submit a
       <A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/peer.txt">peer evaluation form</A>.


  </LI></OL>
  
  <P><STRONG>Please read the message board for clarifications and possible
    answers to questions you might have.</STRONG>

  </P><P class="dataFollows">Notice: GDB can be very useful for this exercise.</P>
  <UL>
    <LI>Use <CODE>break* 0x26000</CODE> to set a breakpoint at address
      0x26000.</LI>

    <LI>Use <CODE>display /i $pc</CODE> to print out the next assembly
      instruction to be executed.</LI>
    <LI>Use <CODE>stepi</CODE> or <CODE>nexti</CODE> for per assembly
      instruction control (similar to step / next on the C level).</LI>
     <LI>Use <CODE>where after receiving a
       <CODE>SIGILL</CODE>/<CODE>SIGSEGV</CODE> to print the call stack.</CODE></LI><CODE>

    <LI>The program stops upon <CODE>SIGILL</CODE>/<CODE>SIGSEGV</CODE> (by
      default) before it gets to the signal handler. Set a breakpoint in your
      signal handler. Use <CODE>continue</CODE> to advance execution to this
      breakpoint.</LI>
  </CODE></UL><CODE>

  <H2>Grading, comments, working in groups, turn in assignments etc.</H2>

  <P>See <A href="http://www.courses.ncsu.edu/csc501/lec/001/hw/hw1/">homework 1</A> for details.</P>

  <P class="dataFollows">Make sure you include the author information:</P>
  <PRE>Single Author info:
  username FirstName MiddleInitial LastName
Group info:
  username FirstName MiddleInitial LastName
  username FirstName MiddleInitial LastName
  username FirstName MiddleInitial LastName</PRE>



  

</CODE></BODY></HTML>